package com.datastructure2.jashtable;

import java.util.*;

/**
 * @author: 临晖
 * @date: 2023/12/20
 * @description:
 */
public class Solution {


    /**
     * 242. 有效的字母异位词
     * 简单
     * 876
     * 相关企业
     * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     * 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
     * 示例 1:
     * 输入: s = "anagram", t = "nagaram"
     * 输出: true
     * 示例 2:
     * 输入: s = "rat", t = "car"
     * 输出: false
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] hash = new int[26];

        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
            hash[t.charAt(i) - 'a']--;
        }

        for (int i = 0; i < hash.length; i++) {
            if (hash[i] != 0) {
                return false;
            }
        }

        return true;
    }


    /**
     * 383. 赎金信
     * 简单
     * 823
     * 相关企业
     * 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
     * 如果可以，返回 true ；否则返回 false 。
     * magazine 中的每个字符只能在 ransomNote 中使用一次。
     *
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        //每个字母只能用一次
        if (ransomNote.length() > magazine.length()) {
            return false;
        }

        int[] hash = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            hash[magazine.charAt(i) - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            if (--hash[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }

        return true;
    }


    /**
     * 49. 字母异位词分组
     * 中等
     * 1.8K
     * 相关企业
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     * <p>
     * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     *
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String newStr = new String(chars);
            List<String> value = map.getOrDefault(newStr, new ArrayList<String>());
            value.add(str);
            map.put(newStr, value);
        }

        return new ArrayList<>(map.values());

    }


    /**
     * 438. 找到字符串中所有字母异位词
     * 中等
     * 1.4K
     * 相关企业
     * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
     * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
     * 示例 1:
     * <p>
     * 输入: s = "cbaebabacd", p = "abc"
     * 输出: [0,6]
     * 解释:
     * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
     * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
     * 示例 2:
     * <p>
     * 输入: s = "abab", p = "ab"
     * 输出: [0,1,2]
     * 解释:
     * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
     * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
     * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
     *
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        int lenS = s.length();
        int lenP = p.length();
        ArrayList<Integer> ans = new ArrayList<>();
        if (lenP > lenS) {
            return ans;
        }

        int[] hashS = new int[26];
        int[] hashP = new int[26];
        for (int i = 0; i < lenP; i++) {
            hashS[s.charAt(i) - 'a']++;
            hashP[p.charAt(i) - 'a']++;
        }

        if (Arrays.equals(hashS, hashP)) {
            ans.add(0);
        }


        for (int i = 0; i < lenS - lenP; i++) {
            hashS[s.charAt(i) - 'a']--;
            hashS[s.charAt(i + lenP) - 'a']++;
            if (Arrays.equals(hashS, hashP)) {
                ans.add(i + 1);
            }

        }

        return ans;
    }


    /**
     * 349. 两个数组的交集
     * 简单
     * 865
     * 相关企业
     * 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        //创建hash对象：特点是不能存入相同的值，即，存入的值是唯一的
        HashSet<Integer> hash = new HashSet<>();
        //将nums1中的值存入hashset中
        for (int i = 0; i < nums1.length; i++) {
            hash.add(nums1[i]);
        }
        //存储俩个数组交集的集合，注意这里用的也是hash，如果搞不懂的话，可自己自己换成list试一下，建议实操一下，对这道题的理解会更加深刻
        HashSet<Integer> res = new HashSet<>();
        //遍历nums2，看hash中是否包含nums2
        for (int i = 0; i < nums2.length; i++) {
            if (hash.contains(nums2[i])) {
                res.add(nums2[i]);
            }
        }

        //将集合中的值导入数组中
        int[] ans = new int[res.size()];
        int count = 0;
        for (Integer value : res) {
            ans[count++] = value;
        }

        return ans;
    }


    /**
     * 350. 两个数组的交集 II
     * 简单
     * 1K
     * 相关企业
     * 给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        //key:值 value: key的出现次数
        HashMap<Integer, Integer> map = new HashMap<>();
        //将nums1中的每个值存入map
        for (int num : nums1) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //返回结果集，先存入list，之后在转成数组，这里不直接定义数组是因为，我们开始不知道返回的结果集有多少值，也就是目前我们无法确定数组的大小
        ArrayList<Integer> list = new ArrayList<>();
        //遍历nums2中的每个值
        for (int num : nums2) {
            //看map中是包含该值
            if (map.containsKey(num)) {
                //如果包含，说明该值就是俩个数组共有的值
                list.add(num);
                //这里需要更该一下map中num对应的个数，
                Integer value = map.get(num);
                value--;
                if (value == 0) {
                    //如果value等于0，那么我们将当前值从map中移除
                    map.remove(num);
                } else {
                    map.put(num, value);
                }
            }
        }

        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }

        return ans;
    }


    /**
     * 202. 快乐数
     * 简单
     * 1.5K
     * 相关企业
     * 编写一个算法来判断一个数 n 是不是快乐数。
     * 「快乐数」 定义为：
     * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
     * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
     * 如果这个过程 结果为 1，那么这个数就是快乐数。
     * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
     *
     * @param n
     * @return
     */
    public boolean isHappy(int n) {
        //创建hashset
        HashSet<Integer> set = new HashSet<>();


        //n如果是快乐数，那么他最终就会等于1
        //n如果不是快乐数，那么它就会无限循环，即，某一个已经出现的数字，还会继续出现，那我们只需要判断，新出现的数字，是否已经出现过，如果出现过，那它就不是快乐数
        while (n != 1 && !set.contains(n)) {
            set.add(n);
            n = getRes(n);
        }
        return n == 1;
    }

    /**
     * 先拆分，在获取和
     *
     * @param n
     * @return
     */
    public int getRes(int n) {
        int sum = 0;
        while (n != 0) {
            sum += ((n % 10) * (n % 10));
            n /= 10;
        }
        return sum;
    }


    /**
     * 1. 两数之和
     * 提示
     * 简单
     * 18.1K
     * 相关企业
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     * <p>
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * <p>
     * 你可以按任意顺序返回答案。
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {

        //创建map集合，key存放数值，value存放数值对应下标
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int dif = target - nums[i];
            if (map.containsKey(dif)) {
                return new int[]{i, map.get(dif)};
            }
            map.put(nums[i], i);
        }

        return null;
    }


    /**
     *
     *454. 四数相加 II
     * 中等
     * 941
     * 相关企业
     * 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
     * 0 <= i, j, k, l < n
     * nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
     *
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {

        HashMap<Integer, Integer> map = new HashMap<>();
        //记录返回值
        int count = 0;

        //将nums1与nums2分别相加，然后放入map集合
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sum = nums1[i] + nums2[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

        //这里利用俩数相加之和的原理
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sum = nums3[i] + nums4[j];
                if (map.containsKey(0 - sum)) {
                    count += map.get(sum);
                }
            }
        }


        return count;

    }


    /**
     *
     * 15. 三数之和
     * 提示
     * 中等
     * 6.6K
     * 相关企业
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     * 你返回所有和为 0 且不重复的三元组。
     * 注意：答案中不可以包含重复的三元组。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        //先排序
        Arrays.sort(nums);
        ArrayList<List<Integer>> list = new ArrayList<>();


        for (int i = 0; i < nums.length; i++) {
            //这里如果nums[i]大于零，那就没有必要继续循环了，这要是开头排序的目的所在
            //因为，三个数相加等于零，升序数组，如果第一个数字都大于零的话，哪么他之后的另外俩个数值也肯定大于零
            //三个正数相加肯定大于零
            if (nums[i] > 0) {
                break;
            }

            //这里还要去重
            //如果上个数字和当前数字相等的话，那么就没必要再去找剩余的俩个数字了
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //去重
                    while (left  < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }

            }
        }
        return list;
    }


    /**
     *
     * 18. 四数之和
     * 中等
     * 1.8K
     * 相关企业
     * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
     * 0 <= a, b, c, d < n
     * a、b、c 和 d 互不相同
     * nums[a] + nums[b] + nums[c] + nums[d] == target
     * 你可以按 任意顺序 返回答案 。
     *
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        ArrayList<List<Integer>> ans = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {

            //剪枝，排序过后，如果开头的数都大于0， 那么四数之和肯定大于零
            if (nums[i] > target && (nums[i] > 0 || target > 0)) {
                break;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            for (int j = i + 1; j < nums.length; j++) {
                //剪枝
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                if (nums[i] + nums[j] > target && (nums[i] + nums[j] > 0 || target > 0)) {
                    break;
                }

                int left = j + 1;
                int right = nums.length - 1;

                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }

                        while (right > left && nums[right] == nums[right - 1]) {
                            right--;
                        }

                        left++;
                        right--;
                    }
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Solution so = new Solution();

    }

}
